// Package _3__二叉搜索树的后序遍历序列 main
// @Title _3__二叉搜索树的后序遍历序列
// @Description
// @Author  == 琳琳也叫王木木 ==  2022-02-10 11:40
// @Create  2022-02-10 11:40
package main

import (
	"fmt"
	"math"
)

/**
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
*/

/**
1. 递归
2.单调栈
*/

//
//  useRecursion
//  @Description: 使用递归解决这个问题
//
func useRecursion(postorder []int) bool {
	var dfs func(nums []int, i, j int) bool
	dfs = func(nums []int, i, j int) bool {
		if i >= j {
			return true
		}
		p := i
		for nums[p] < nums[j] {
			p++
		}
		t := p
		for nums[p] > nums[j] {
			p++
		}
		return p == j && dfs(nums, i, t-1) && dfs(nums, t, j-1)
	}
	return dfs(postorder, 0, len(postorder)-1)
}

func useStack(postorder []int) bool {
	myStack := []int{}
	root := math.MaxInt32
	for i := len(postorder) - 1; i >= 0; i-- {
		if postorder[i] > root {
			return false
		}
		for len(myStack) > 0 && postorder[i] < myStack[len(myStack)-1] {
			root = myStack[len(myStack)-1]
			myStack = myStack[:len(myStack)-1]
			//fmt.Println(myStack)
		}
		myStack = append(myStack, postorder[i])
	}
	return true
}

func verifyPostorder(postorder []int) bool {
	return false
}

func main() {
	//fmt.Println(useRecursion([]int{1,6,3,2,5}))
	//fmt.Println(useRecursion([]int{1,3,2,6,5}))
	fmt.Println(useStack([]int{1, 6, 3, 2, 5}))
	fmt.Println(useStack([]int{1, 3, 2, 6, 5}))
}
